U.S. Pat. Nos. 5,611,049, 5,892,914, 6,026,452, 6,085,234 and 6,205,475 disclose methods and devices used in a networked, multi-processor digital computer system for caching images of files at various computers within the system. All five (5) United States patents are hereby incorporated by reference as though fully set forth here.
FIG. 1 is a block diagram depicting such a networked, multi-processor digital computer system that is referred to by the general reference character 20. The digital computer system 20 includes a Network Distributed Cache (“NDC”) server site 22, an NDC client site 24, and a plurality of intermediate NDC sites 26A and 26B. Each of the NDC sites 22, 24, 26A and 26B in the digital computer system 20 includes a processor and RAM, neither of which are illustrated in FIG. 1. Furthermore, the NDC server site 22 includes a disk drive 32 for storing data that may be accessed by the NDC client site 24. The NDC client site 24 and the intermediate NDC site 26B both include their own respective hard disks 34 and 36. A client workstation 42 communicates with the NDC client site 24 via an Ethernet, 10BaseT or other type of Local Area Network (“LAN”) 44 in accordance with a network protocol such as a Server Message Block (“SMB”), Network File System (“NFS®”), Hyper-Text Transfer Protocol (“HTTP”), Netware Core Protocol (“NCP”), or other network-file-services protocol.
Each of the NDC sites 22, 24, 26A and 26B in the networked digital computer system 20 includes an NDC 50 depicted in an enlarged illustration adjacent to intermediate NDC site 26A. The NDCS 50 in each of the NDC sites 22, 24, 26A and 26B include a set of computer programs and a data cache located in the RAM of the NDC sites 22, 24, 26A and 26B. The NDCs 50 together with Data Transfer Protocol (“DTP”) messages 52, illustrated in FIG. 1 by the lines joining pairs of NDCs 50, provide a data communication network by which the client workstation 42 may access data on the disk drive 32 via the chain of NDC sites 24, 26B, 26A or 22NDC sites 24, 26B, 26A and 22.
The NDCs 50 operate on a data structure called a “dataset.” Datasets are named sequences of bytes of data that are addressed by:                a server-id that identifies the NDC server site where source data is located, such as NDC server site 22; and        a dataset-id that identifies a particular item of source data stored at that site, usually on a hard disk, such as the disk drive 32 of the NDC server site 22.Topology of an NDC Network        
An NDC network, such as that illustrated in FIG. 1 having NDC sites 22, 24, 26A and 26B, includes:                1. all nodes in a network of processors that are configured to participate as NDC sites; and        2. the DTP messages 52 that bind together NDC sites, such as NDC sites 22, 24, 26A and 26B.Any node in a network of processors that possesses a megabyte or more of surplus RAM may be configured as an NDC site. NDC sites communicate with each other via the DTP messages 52 in a manner that is completely compatible with non-NDC sites.        
FIG. 1 depicts a series of NDC sites 22, 24, 26A and 26B linked together by the DTP messages 52 that form a chain connecting the client workstation 42 to the NDC server site 22. The NDC chain may be analogized to an electrical transmission line. The transmission line of the NDC chain is terminated at both ends, i.e., by the NDC server site 22 and by the NDC client site 24. Thus, the NDC server site 22 may be referred to as an NDC server terminator site for the NDC chain, and the NDC client site 24 may be referred to as an NDC client terminator site for the NDC chain. An NDC server terminator site 22 will always be the node in the network of processors that “owns” the source data structure. The other end of the NDC chain, the NDC client terminator site 24, is the NDC site that receives requests from the client workstation 42 to access data on the NDC server site 22.
Data being written to the disk drive 32 at the NDC server site 22 by the client workstation 42 flows in a “downstream” direction indicated by a downstream arrow 54. Data being loaded by the client workstation 42 from the disk drive 32 at the NDC server site 22 is pumped “upstream” through the NDC chain in the direction indicated by an upstream arrow 56 until it reaches the NDC client site 24. When data reaches the NDC client site 24, it together with metadata is reformatted into a reply message in accordance with the appropriate network protocol such as NFS, and sent back to the client workstation 42. NDC sites are frequently referred to as being either upstream or downstream of another NDC site. If consistent images of files are to be projected from NDCs 50 operating as server terminators to other NDCs 50 throughout the digital computer system 20, the downstream NDC site 22, 26A or 26B must be aware of the types of activities being performed at its upstream NDC sites 26A, 26B or 24 at all times.
As described in the patents identified above, for the networked digital computer system 20 depicted in FIG. 1, a single request by the client workstation 42 to read data stored on the disk drive 32 is serviced as follows.                1. The request flows across the LAN 44 to the NDC client terminator site 24 which serves as a gateway to the chain of NDC sites 24, 26B, 26A and 22. Within the NDC client terminator site 24, NDC client intercept routines 102, illustrated in greater detail in FIG. 2, inspect the request. If the request is an NFS request and if the request is directed at any NDC sites 24, 26B, 26A or 22 for which the NDC client terminator site 24 is a gate-way, then the request is intercepted by the NDC client intercept routines 102.        2. The NDC client intercept routines 102 converts the NFS request into a DTP request, and then submits the request to an NDC core 106.        3. The NDC core 106 in the NDC client terminator site 24 receives the request and checks its NDC cache to determine if the requested data is already present there. If all data is present in the NDC cache of the NDC client terminator site 24, the NDC 50 will copy pointers to the data into a reply message structure and immediately respond to the calling NDC client intercept routines 102.        4. If all the requested data isn't present in the NDC cache of the NDC client terminator site 24, then the NDC 50 of the NDC client terminator site 24 accesses elsewhere any missing data. If the NDC client terminator site 24 were a server terminator site, then the NDC 50 would access the file system for the hard disk 34 upon which the data would reside.        5. Since the NDC client site 24 is a client terminator site rather than a server terminator site, the NDC 50 must request the data it needs from the next downstream NDC site, i.e., intermediate NDC site 26B in the example depicted in FIG. 1. Under this circumstance, DTP client interface routines 108, illustrated in FIG. 2, are invoked to request from the intermediate NDC site 26B whatever additional data the NDC client terminator site 24 needs to respond to the current request.        6. A DTP server interface routines 104, illustrated in FIG. 2, at the downstream intermediate NDC site 26B receives the request from the NDC 50 of the NDC client terminator site 24 and processes it according to steps 3, 4, and 5 above. The preceding sequence repeats for each of the NDC sites 24, 26B, 26A and 22 in the NDC chain until the request reaches the server terminator, i.e., NDC server site 22 in the example depicted in FIG. 1, or until the request reaches an intermediate NDC site that has cached all the data that is being requested.        7. When the NDC server terminator site 22 receives the request, its NDC 50 accesses the source data structure. If the source data structure resides on a hard disk, the appropriate file system code (UFS, DOS, etc.) is invoked to retrieve the data from the disk drive 32.        8. When the file system code on the NDC server terminator site 22 returns the data from the disk drive 32, a response chain begins whereby each downstream site successively responds upstream to its client, e.g. NDC server terminator site 22 responds to the request from intermediate NDC site 26A, intermediate NDC site 26A responds to the request from intermediate NDC site 26B, etc.        9. Eventually, the response percolates up through the sites 22, 26A, and 26B to the NDC client terminator site 24.        10. The NDC 50 on the NDC client terminator site 24 returns to the calling NDC client intercept routines 102, which then packages the returned data and metadata into an appropriate network protocol format, such as that for an NFS reply, and sends the data and metadata back to the client workstation 42.The NDC 50        
As depicted in FIG. 2, the NDC 50 includes five major components:                NDC client intercept routines 102;        DTP server interface routines 104;        NDC core 106;        DTP client interface routines 108; and        file system interface routines 112.        
Routines included in the NDC core 106 implement the function of the NDC 50. The other routines 102, 104, 108 and 112 supply data to and/or receive data from the NDC core 106. FIG. 2 illustrates that the NDC client intercept routines 102 are needed only at NDCs 50 which may receive requests for data in a protocol other than DTP, e.g., a request in NFS protocol, SMB protocol, or another protocol. The NDC client intercept routines 102 are completely responsible for all conversions necessary to interface a projected dataset image to a request that has been submitted via any of the industry standard protocols supported at the NDC sites 24, 26B, 26A or 22.
The file system interface routines 112 are necessary in the NDC 50 only at NDC file server sites, such as the NDC server terminator site 22. The file system interface routines 112 route data between the disk drives 32A, 32B and 32C illustrated in FIG. 2 and a data conduit provided by the NDCs 50 that extends from the NDC server terminator site 22 to the NDC client terminator site 24.
If the NDC client intercept routines 102 of the NDC 50 receives a request to access data from a client, such as the client workstation 42, it prepares a DTP request indicated by an arrow 122 in FIG. 2. If the DTP server interface routines 104 of the NDC 50 receives a request from an upstream NDC 50, it prepares a DTP request indicated by the arrow 124 in FIG. 2. The DTP requests 122 and 124 are presented to the NDC core 106. Within the NDC core 106, the requests 122 or 124 cause a buffer search routine 126 to search a pool 128 of NDC buffers 129, as indicated by the arrow 130 in FIG. 2, to determine if all the data requested by either the routines 102 or 104 is present in the NDC buffers 129 of this NDC 50. If all the requested data is present in the NDC buffers 129, the buffer search routine 126 prepares a DTP response, indicated by the arrow 132 in FIG. 2, that responds to the requests 122 or 124, and the NDC core 106 appropriately returns the DTP response 132, containing both data and metadata, either to the NDC client intercept routines 102 or to the DTP server interface routines 104 depending upon which routine 102 or 104 submitted the requests 122 or 124. If the NDC client intercept routines 102 receives DTP response 132, before the NDC client intercept routines 102 returns the requested data and metadata to the client workstation 42 it reformats the response from DTP to the protocol in which the client workstation 42 requested access to the dataset, e.g. into NFS, SMB, Netware or any other protocol.
If all the requested data is not present in the NDC buffers 129, then the buffer search routine 126 prepares a DTP downstream request, indicated by the arrow 142 in FIG. 2, for only that data which is not present in the NDC buffers 129. A request director routine 144 then directs the DTP request 142 to the DTP client interface routines 108, if this NDC 50 is not located in the NDC server terminator site 22, or to the file system interface routines 112, if this NDC 50 is located in the NDC server terminator site 22. After the DTP client interface routines 108 obtains the requested data together with its metadata from a downstream NDC site 22, 26A, etc. or the file system interface routines 112 obtains the data from the file system of this NDC client terminator site 24, the data is stored into the NDC buffers 129 and the buffer search routine 126 returns the data and metadata either to the NDC client intercept routines 102 or to the DTP server interface routines 104 as described above.
In addition to projecting images of a stored dataset, the NDCs 50 detect a condition for a dataset, called a concurrent write sharing (“CWS”) condition, whenever two or more client sites concurrently access a dataset, and one or more of the client sites attempts to write the dataset. If a CWS condition occurs, one of the NDC sites, such as the NDC sites 22, 24, 26A and 26B in the digital computer system 20, declares itself to be a consistency control site (“CCS”) for the dataset, and imposes restrictions on the operation of other NDCs 50 upstream from the CCS. The operating restrictions that the CCS imposes upon upstream NDCs 50 guarantee throughout the network of digital computers that client sites, such as the client workstation 42, have the same level of file consistency as they would have if all the client sites operated on the same computer. That is, the operating conditions that the CCS imposes ensure that modifications made to a dataset by one client site are reflected in the subsequent images of that dataset projected to other client sites no matter how far the client site modifying the dataset is from the client site that subsequently requests to access the dataset.
While the United States patents identified above disclose how images of files may be cached at various computers within the system in the digital computer system 20 and how operation of NDCs 50 preserve consistent images of the files throughout the digital computer system 20, the disclosures of those patents omits any discussion of problems which arise in managing assess to files stored at various locations throughout the digital computer system 20.